#include <stdio.h>
#include <stdlib.h>
#include "omp.h"
#include "tbb/parallel_for.h"
#include "tbb/mutex.h"
#include "tbb/blocked_range2d.h"
#include <cstring>

int matrix_counter;
int max_relabels = 362880;
int nThreads = 16;

tbb::mutex dataMutex;

class matrix {

public:
	char *data;
	int counter;
	/*
	 * data filled like
	 * 1 2 3 4 5 6 7 8 9
	 * 10 11 12 ...
	 */

	/* Implement consistent memory allocation for matrices */
	matrix (char Tdata[81])
	{
		data = new char [81];
		memcpy(data, Tdata, 81);
		counter = ++matrix_counter;
	}

	matrix(matrix& o) {
		operator=(o);
		counter = matrix_counter;
		++matrix_counter;
	}
	~matrix() {
		//if(data != NULL) delete[] data;
		delete[] data;
	}

	void operator=(matrix* o) {
		if(data == NULL) {
			delete[] data;
		}

		data = new char[81];
		memcpy(data, o->data, 81);
		counter = o->counter;
	}
};

class relabelSet {
	matrix *items;
	int size;

public:
	relabelSet(char puzzle [81])
	{
		size = (max_relabels+1);
		items = (matrix*)malloc(sizeof(matrix)*(max_relabels+1));
		char map[9] = {1,2,3,4,5,6,7,8,9};
		char newPuzzle[81];
		//items[max_relabels+1] = new matrix(newPuzzle);
		items[max_relabels] = new matrix(puzzle);
		//Go through till extra finding a new permutation
		for(int i=0;i < max_relabels;i++)
		{
			for(int j = 0; j < 81; ++j)
				newPuzzle[j] = map[puzzle[j]-1];
			items[i] = new matrix(newPuzzle);
			if(next_permutation (map,9)==1)
				return;
		}

		return;
	}
	int uniqueSets ()
	{
		double start, end;
		int goUpTo = 20; //or size
		start = omp_get_wtime();
		int i, j;

	#ifdef PARALLEL
		tbb::parallel_for(tbb::blocked_range<size_t>(0,goUpTo),uniqSetLoop(&size,items,this));
	#elif defined OMP
	#pragma omp parallel for private(j) num_threads(nThreads)
	#endif
		for (i = 0; i < goUpTo; ++i)
		{
			for (j = size - 1; j > i; --j)
			{
				checkMember (&items[i],&items[j]);
			}
			printf("Up to %d\n",i);
		}
		end = omp_get_wtime();
		printf("The time to find all unique sets took %f seconds\n",end-start);
		return size;


	}

	class uniqSetLoop
	{
		int *const mySize;
		matrix *myItems;
		relabelSet *const myParent;
	public:

		uniqSetLoop(int *theSize,matrix *theItems,relabelSet* theParent):
			mySize(theSize),
			myItems(theItems),
			myParent(theParent)
			{
			}
		void operator()(const tbb::blocked_range<size_t> &r)const
		{

			for (size_t i = r.begin(); i < r.end(); ++i)
			{
				//myParent->print_puzzle(myItems[i].data);
				for (int j = myParent->size - 1; j > i; --j)
				{
					myParent->checkMember (&myItems[i],&myItems[j]);
				}
				//myParent->print_puzzle(myItems[i].data);
				printf("Up to %lu\n",i);
			}
		}
	};

	void checkMember (matrix* a, matrix *b) {
		dataMutex.lock();
		int bNumber = b->counter;
		int sizeNow = size;
		dataMutex.unlock();
		for (char i = 0; i < 9;++i)
		{


			if (i%3 == 1)
				for (char j =0; j < 3;++j)
					swapColumn(a,0+j,3+j);
			else if (i % 3 == 2)
				for (char j =0; j < 3;++j)
					swapColumn(a,3+j,6+j);
			else if (i > 0)
			{
				for (char j =0; j < 3;++j)
					swapColumn(a,6+j,0+j);
				if (i/3 == 1)
					for (char j =0; j < 3;++j)
						swapRow(a,j,3+j);
				else // We know i% 3 == 0 and i > 0 thus i/3 = 2
					for (char j =0; j < 3;++j)
						swapRow(a,3+j,6+j);
			}

			if ((permutate (i, a, b)==1)) {
				if ((bNumber == b->counter)&&(sizeNow == size))
				{
					dataMutex.lock();
					printf("Found copy with block %d and %d\n",a->counter,b->counter);
					*b = items[size-1];
					--size;
					dataMutex.unlock();
					return;
				}
			}

		}
		rotate (a);
		for (char i = 0; i < 9;++i)
		{


			if (i%3 == 1)
				for (char j =0; j < 3;++j)
					swapColumn(a,0+j,3+j);
			else if (i % 3 == 2)
				for (char j =0; j < 3;++j)
					swapColumn(a,3+j,6+j);
			else if (i > 0)
			{
				for (char j =0; j < 3;++j)
					swapColumn(a,6+j,0+j);
				if (i/3 == 1)
					for (char j =0; j < 3;++j)
						swapRow(a,j,3+j);
				else // We know i% 3 == 0 and i > 0 thus i/3 = 2
					for (char j =0; j < 3;++j)
						swapRow(a,3+j,6+j);
			}

			if ((permutate (i, a, b)==1)) {
				if ((bNumber == b->counter)&&(sizeNow == size))
				{
					dataMutex.lock();
					printf("Found copy with block %d and %d\n",a->counter,b->counter);
					*b = items[size-1];
					--size;
					dataMutex.unlock();
					return;
				}
			}

		}
	}
	/*
	 * input:
	 * 	i in (0..8) and is what block number we are trying
	 * 	A is the first matrix
	 * 	B is the second matrix we are trying to make A into
	 * return:
	 *  1: if A in PermSet(B)
	 *  0: else
	 */
	char permutate (char i, matrix* a, matrix* B) {
		//matrix* a = new matrix(A->data);//This way we don't touch original a
		//Doesn't help, and doesn't matter
		char y = 3*(i/3);//Row Index
		char x = 3*(i%3);//Column Index
		char* tempA = &(a->data[9*x + y]);
		char* tempB;
		char breakValue = 0;
		char j,k,l;
		char fixStart,fixEnd;



	// ***p2 Make block fit
		if (fixBlock(a,B,x,y,0)==0)
			return 0;
	// ***p3 make band fit

		//find j such that a_(0,y) = b_(j,y)

		for (j = 3; j < 9; ++j)
			if (a->data[x +3 + 9*y] ==B->data[(x+j)%9 + 9*y])
				break;



		//Move block to correct side and match up above

		if (j > 5)//Need to swap blocks 3 and 5
			for (k = 0;k < 3;++k)
				swapColumn(a,(x+3)%9+k,(x+6)%9 + k);

		if (fixBlock(a,B,0,y,1)==0)
			return 0;

	// ***p4 make pillar fit


		//find j such that a_(0,y) = b_(j,y)

		for (j = 3; j < 9; ++j)
			if (a->data[x + 9*(y+3)] ==B->data[x + 9*((y+j)%9)])
				break;



		//Move block to correct side and match up above

		if (j > 5)//Need to swap blocks 3 and 5
			for (k = 0;k < 3;++k)
				swapRow(a,(y+3)%9+k,(y+6)%9 + k);

		if (fixBlock(a,B,0,y,2)==0)
			return 0;
	// ***p5 check rest
		for (j = 0; j < 6; j += 3)
			for (k = 0; k < 6 ; k += 3)
				if (checkBlock (a,B,(x+j)%9,(y+k)%9) == 0)
					return 0;
		return 1;

	}

	private:
	matrix* rotate (matrix *a)
	{
		char temp;
		for (int i = 0; i < 4;++i)
		{
			for (int j = 9 - 1 - i; j > i; --j)
			{
				temp = a->data[i*9+j];
				a->data[i*9+j] = a->data[9*(8-j) + i];
				a->data[9*(8-j) + i] =a->data[9*(8-i) + 8-j];
				a->data[9*(8-i) + 8-j] = a->data[9*(j) + 8-i];
				a->data[9*(j) + 8-i] = temp;
			}
		}
	}
	char checkBlock (matrix* a,matrix* b, char x, char y)
	{
		for (int i = 0; i < 3;++i)
			for (int j = 0; j < 3;++j)
				if (a->data[x+i+9*(y+j)]!=b->data[x+i+9*(y+j)])
					return 0;
		return 1;
	}

	/*
	 * input:
	 * 	a is the puzzle
	 * 	x,y are the ul corner of the block
	 * 	fixedPoint: 0 is no fixed, 1 is column fixed, 2 is row fixed
	 * results:
	 * 	returns 1 if good, 0 if not able to fix block
	 */
	char fixBlock (matrix* a,matrix* b, char x, char y, char fixedPoint)
	{
		char addToPointer = 1;
		char *tempa, *tempb;
		char fixStart, fixEnd;
		char i,j,k;

		if (fixedPoint == 2)
			addToPointer = 9;



		if (fixedPoint == 0)
		{
			tempa = &(a->data[x+9*y]);
			//Get first row fixed
			for (j = 0; j < 3; ++j)//row
				for (k = 0; k < 3; ++k)//column
					if (*tempa == b->data[x+k + 9*(j+y)])
					{
						if (k != 0)
							swapColumn (a,x,x+k);
						if (j != 0)
							swapRow (a, y,y + j);
						goto breakOut1;
					}
			breakOut1:{}

			tempa = &(a->data[x+9*(y+j)])+1;
			tempb = &(b->data[x+9*(y+j)])+1;

			//Get rest of row fixed
			if (*(tempa) != *(tempb))
			{
				if (*(tempa+1) != *(tempb))//a_(x+1,y+j) != b_(x+1,y+j) != a_(x+2,y+j)
					return 0;
				swapColumn(a,x+1,x+2);
			}
		}
		else
		{
			tempa = &(a->data[x+9*(y)]);
			tempb = &(b->data[x+9*(y)]);
			//Get first row fixed
			for (j = 0; j < 3; ++j)
				if(*tempa == *(tempb+addToPointer * j))
				{
					if (addToPointer == 1)
						swapColumn (a,x,x+j);
					else
						swapRow(a,y,y+j);
					break;
				}

			tempa += addToPointer * j;
			tempb += addToPointer * j;
		}

		//Check if locked in row/column
		if (*(tempa+=addToPointer) != *(tempb += addToPointer))
			return 0;

		if (*(tempa+=addToPointer) != *(tempb += addToPointer))
			return 0;

		fixStart = 0;
		fixEnd = 2*addToPointer;
		tempa = &(a->data[x+9*y]);
		tempb = &(b->data[x+9*y]);
		if (j == 0)
			fixStart += addToPointer;
		else if (j==2)
			fixEnd -= addToPointer;

		if (*(tempa+fixStart) != *(tempb + fixStart))// a_(fixStart,y) \neq b_(fixStart,y)
		{
			if (*(tempa+fixEnd) != *(tempb + fixStart))// a_(fixEnd,y) \neq b_(fixStart,y)
				return 0;
			if(fixedPoint == 2)
				swapRow(a,y+fixStart,y+fixEnd);
			else
				swapColumn(a,x+fixStart,x+fixEnd);
		}
		if (*(tempa+fixEnd) != *(tempb + fixEnd))// a_(fixEnd,y) \neq b_(fixEnd,y)
			return 0;

		if (fixedPoint == 2)
			addToPointer = 1;
		else
			addToPointer = 9;

		for (k = 0; k < 2;k+=addToPointer)
			if (*(tempa+fixStart + k) != *(tempb + fixStart + k))
				return 0;
			if (*(tempa+fixEnd + k) != *(tempb + fixEnd + k))
				return 0;


		return 1;
	}
	/*
	 * input:
	 * 	puzzle is the matrix/sudoku that we are going to change
	 *  a,b is the row number
	 * results:
	 * 	the rows are swapped
	 */
	void swapRow(matrix* puzzle,char a, char b)
	 {
		 char* point1 = &(puzzle->data[9*a]);
		 char* point2 = &(puzzle->data[9*b]);
		 char temp;
		 for (char i = 0; i < 9; ++i)
		 {
			 temp = *point1;
			 *(point1++) = *point2;
			 *(point2++) = temp;
		 }
	 }
	 /*
	 * input:
	 * 	puzzle is the matrix/sudoku that we are going to change
	 *  a,b is the row number
	 * results:
	 * 	the rows are swapped
	 */
	void swapColumn(matrix* puzzle,char a, char b)
	 {
		 char* point1 = &(puzzle->data[a]);
		 char* point2 = &(puzzle->data[b]);
		 char temp;
		 for (char i = 0; i < 9; ++i)
		 {
			 temp = *point1;
			 *(point1) = *point2;
			 point1 += 9;
			 *(point2) = temp;
			 point2 += 9;
		 }
	 }
	/*
	 * input:
	 *  list is an ordered list, may not be in order
	 *  listSize is the size of list
	 * return:
	 *  0 if it could find next
	 *  1 if it could not find
	 */
	int next_permutation (char * list, int listSize) {
		//Used a lexigraphic permutation algorithm
		char i,j,temp;
		char *first,*last;

		for (i = listSize-2; i >= 0; --i) { //find biggest i such that l[i]<l[i+1]
			if(list[i]<list[i+1]) {
				break;
			}
		}
		temp=list[i];

		if (i < 0) {//reached last lexigraphic permutation
			return 1;
		}

		j = listSize - 1;
		while (1) { //find biggest j such that l[i]<l[j]
			if (temp < list[j]) {
				break;
			}
			--j;
		}

		//swap
		list[i] = list[j];
		list[j] = temp;
		first = &list[i+1];

		//reverse all {l[x] | x > i and l[x]\in l}
		last = &list[listSize-1];
		while(first < last) {
			temp = *first;
			*(first++)=*last;
			*(last--)=temp;
		}
		return 0;

	}
	void print_puzzle (char puzzle[81])
	{
		int i,j;
		printf("-------------------------------------\n");
		for (i = 0; i < 9;++i)
		{
			for (j = 0;j < 9;++j)
			{
				printf("| %d ",puzzle[i*9+j]);
			}
			printf("|\n-------------------------------------\n");
		}
	}

};



int main(int argc, char **argv) {

	if (argc != 82)
	{
		printf("We have an invalid number of inputs, we have %d and need 81 inputs",argc-1);
		return 1;
	}
	int i;
	char data [81];
	for(i = 0; i < 81; ++i)
		data[i] = atoi(argv[i+1]);
	relabelSet* mySet = new relabelSet (data);
	i = 0;
	printf("We have %lld unique set\n", (long long) mySet->uniqueSets());


}
